package com.algorithm.ch1.cjm.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 验证回文字符串
 * “回文串”是一个正读和反读都一样的字符串
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 * <p>
 * 说明：本题中，我们将空字符串定义为有效的回文串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "race a car"
 * 输出: false
 */
public class IsPalindrome {

    public static void main(String[] args) {

        boolean flag = new IsPalindrome().isPalindrome1("A man, a plan, a canal: Panama");

        System.out.println(flag);
    }

    /**
     * T(n) = n + n/2
     * f(n) = n
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        if(s == null){
            return false;
        }
        if(s.length() == 1){
            return true;
        }

        char[] chars = s.toCharArray();

        //得到需要比较的字符
        List<Character> characterList = new ArrayList<>();
        for(char c : chars){

            if(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9'){
                characterList.add(c);
            }
        }

        //数组长度
        int size = characterList.size();

        boolean flag;
        int c;

        //比较数组首尾是否相等
        for (int i = 0; i < size/2; i++) {

            c = characterList.get(i);

            if(c >= '0' && c <= '9'){

                flag = c != characterList.get(size -1 -i);

            }else {

                //'A' 65 'a' 97
                flag = !(c == characterList.get(size -1 -i) || Math.abs(c - characterList.get(size - 1 -i)) == 32);
            }

            if(flag){
                return false;
            }
        }

        return true;
    }


    /**
     * leetcode 最优
     * 位图法 && 双指针法
     * 有限集的数组
     *
     * @param s
     * @return
     */
    public boolean isPalindrome1(String s) {
        char[] sArray = s.toCharArray();
        // 转换成数组
        int[] res = new int[sArray.length];
        int length = 0;
        for (int i = 0; i < sArray.length; i++) {
            if (sArray[i] != ' ') {
                int gapB = sArray[i] - 'A';
                int gapS = sArray[i] - 'a';
                if (gapB >= 0 && gapB <= 25) {
                    res[length++] = gapB + 10;
                } else if (gapS >= 0 && gapS <= 25) {
                    res[length++] = gapS + 10;
                } else if (sArray[i] >= '0' && sArray[i] <= '9') {
                    res[length++] = sArray[i] - '0';
                }
            }
        }

        // 双指针法，判断是否相等
        int start = 0;
        int end = length - 1;
        while (start < end) {
            if (res[start] != res[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

}
